<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<meta http-equiv="Content-Type" content="text/xhtml;charset=UTF-8"/>
<meta http-equiv="X-UA-Compatible" content="IE=9"/>
<title>Data Structures for Sets and Graphs: CoveringAlgorithm Class Reference</title>
<link href="tabs.css" rel="stylesheet" type="text/css"/>
<script type="text/javascript" src="jquery.js"></script>
<script type="text/javascript" src="dynsections.js"></script>
<link href="search/search.css" rel="stylesheet" type="text/css"/>
<script type="text/javascript" src="search/search.js"></script>
<script type="text/javascript">
  $(document).ready(function() { searchBox.OnSelectItem(0); });
</script>
<link href="doxygen.css" rel="stylesheet" type="text/css" />
</head>
<body>
<div id="top"><!-- do not remove this div, it is closed by doxygen! -->
<div id="titlearea">
<table cellspacing="0" cellpadding="0">
 <tbody>
 <tr style="height: 56px;">
  <td style="padding-left: 0.5em;">
   <div id="projectname">Data Structures for Sets and Graphs
   </div>
  </td>
 </tr>
 </tbody>
</table>
</div>
<!-- end header part -->
<!-- Generated by Doxygen 1.8.1.1 -->
<script type="text/javascript">
var searchBox = new SearchBox("searchBox", "search",false,'Search');
</script>
  <div id="navrow1" class="tabs">
    <ul class="tablist">
      <li><a href="index.html"><span>Main&#160;Page</span></a></li>
      <li class="current"><a href="annotated.html"><span>Classes</span></a></li>
      <li><a href="files.html"><span>Files</span></a></li>
      <li>
        <div id="MSearchBox" class="MSearchBoxInactive">
        <span class="left">
          <img id="MSearchSelect" src="search/mag_sel.png"
               onmouseover="return searchBox.OnSearchSelectShow()"
               onmouseout="return searchBox.OnSearchSelectHide()"
               alt=""/>
          <input type="text" id="MSearchField" value="Search" accesskey="S"
               onfocus="searchBox.OnSearchFieldFocus(true)" 
               onblur="searchBox.OnSearchFieldFocus(false)" 
               onkeyup="searchBox.OnSearchFieldChange(event)"/>
          </span><span class="right">
            <a id="MSearchClose" href="javascript:searchBox.CloseResultsWindow()"><img id="MSearchCloseImg" border="0" src="search/close.png" alt=""/></a>
          </span>
        </div>
      </li>
    </ul>
  </div>
  <div id="navrow2" class="tabs2">
    <ul class="tablist">
      <li><a href="annotated.html"><span>Class&#160;List</span></a></li>
      <li><a href="classes.html"><span>Class&#160;Index</span></a></li>
      <li><a href="inherits.html"><span>Class&#160;Hierarchy</span></a></li>
      <li><a href="functions.html"><span>Class&#160;Members</span></a></li>
    </ul>
  </div>
<!-- window showing the filter options -->
<div id="MSearchSelectWindow"
     onmouseover="return searchBox.OnSearchSelectShow()"
     onmouseout="return searchBox.OnSearchSelectHide()"
     onkeydown="return searchBox.OnSearchSelectKey(event)">
<a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(0)"><span class="SelectionMark">&#160;</span>All</a><a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(1)"><span class="SelectionMark">&#160;</span>Classes</a><a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(2)"><span class="SelectionMark">&#160;</span>Files</a><a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(3)"><span class="SelectionMark">&#160;</span>Functions</a><a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(4)"><span class="SelectionMark">&#160;</span>Variables</a><a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(5)"><span class="SelectionMark">&#160;</span>Typedefs</a><a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(6)"><span class="SelectionMark">&#160;</span>Enumerations</a><a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(7)"><span class="SelectionMark">&#160;</span>Enumerator</a><a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(8)"><span class="SelectionMark">&#160;</span>Friends</a><a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(9)"><span class="SelectionMark">&#160;</span>Macros</a></div>

<!-- iframe showing the search results (closed by default) -->
<div id="MSearchResultsWindow">
<iframe src="javascript:void(0)" frameborder="0" 
        name="MSearchResults" id="MSearchResults">
</iframe>
</div>

</div><!-- top -->
<div class="header">
  <div class="summary">
<a href="#pub-methods">Public Member Functions</a> &#124;
<a href="#pub-static-methods">Static Public Member Functions</a>  </div>
  <div class="headertitle">
<div class="title">CoveringAlgorithm Class Reference</div>  </div>
</div><!--header-->
<div class="contents">

<p><code>#include &lt;<a class="el" href="CoveringAlgorithm_8h_source.html">CoveringAlgorithm.h</a>&gt;</code></p>

<p><a href="classCoveringAlgorithm-members.html">List of all members.</a></p>
<table class="memberdecls">
<tr class="heading"><td colspan="2"><h2><a name="pub-methods"></a>
Public Member Functions</h2></td></tr>
<tr class="memitem:aed9685e459071f73af35dfafd116b133"><td class="memItemLeft" align="right" valign="top">long&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="classCoveringAlgorithm.html#aed9685e459071f73af35dfafd116b133">run</a> (<a class="el" href="classGraph.html">Graph</a> *g, long *res, long *R, long r)=0</td></tr>
<tr class="memitem:aabf673011d19a85d51789efa556b0f5c"><td class="memTemplParams" colspan="2">template&lt;class T , typename Z&gt; </td></tr>
<tr class="memitem:aabf673011d19a85d51789efa556b0f5c"><td class="memTemplItemLeft" align="right" valign="top">long&#160;</td><td class="memTemplItemRight" valign="bottom"><a class="el" href="classCoveringAlgorithm.html#aabf673011d19a85d51789efa556b0f5c">dsaturCoverSort</a> (<a class="el" href="classGraph.html">Graph</a>&lt; T &gt; *g, long k, long *rank)</td></tr>
</table><table class="memberdecls">
<tr class="heading"><td colspan="2"><h2><a name="pub-static-methods"></a>
Static Public Member Functions</h2></td></tr>
<tr class="memitem:a22e739e175eaef6218f9a489528488ba"><td class="memTemplParams" colspan="2">template&lt;class T &gt; </td></tr>
<tr class="memitem:a22e739e175eaef6218f9a489528488ba"><td class="memTemplItemLeft" align="right" valign="top">static long&#160;</td><td class="memTemplItemRight" valign="bottom"><a class="el" href="classCoveringAlgorithm.html#a22e739e175eaef6218f9a489528488ba">greedyCoverSort</a> (<a class="el" href="classGraph.html">Graph</a> *g, long **cover, <a class="el" href="classFactory.html">Factory</a>&lt; T &gt; *factory, long *R, long r)</td></tr>
<tr class="memdesc:a22e739e175eaef6218f9a489528488ba"><td class="mdescLeft">&#160;</td><td class="mdescRight">Made a greedy coloring of the subgraph induced by the vertexes in R, with the order that they appear in R.  <a href="#a22e739e175eaef6218f9a489528488ba"></a><br/></td></tr>
<tr class="memitem:a93b9589e1dba6b3533bea7e30a03bf6f"><td class="memTemplParams" colspan="2">template&lt;typename T , template&lt; typename T &gt; class D&gt; </td></tr>
<tr class="memitem:a93b9589e1dba6b3533bea7e30a03bf6f"><td class="memTemplItemLeft" align="right" valign="top">static long&#160;</td><td class="memTemplItemRight" valign="bottom"><a class="el" href="classCoveringAlgorithm.html#a93b9589e1dba6b3533bea7e30a03bf6f">dsaturCoverSort</a> (long n, <a class="el" href="classFactory.html">Factory</a>&lt; D &gt; *factory)</td></tr>
<tr class="memdesc:a93b9589e1dba6b3533bea7e30a03bf6f"><td class="mdescLeft">&#160;</td><td class="mdescRight">Determines a greedy coloring of the subgraph induced by the specified vertices using the <a class="el" href="classDsatur.html">Dsatur</a> algorithm.  <a href="#a93b9589e1dba6b3533bea7e30a03bf6f"></a><br/></td></tr>
<tr class="memitem:a17d51abd33df8a318074b115abecc91f"><td class="memTemplParams" colspan="2">template&lt;class T &gt; </td></tr>
<tr class="memitem:a17d51abd33df8a318074b115abecc91f"><td class="memTemplItemLeft" align="right" valign="top">static long&#160;</td><td class="memTemplItemRight" valign="bottom"><a class="el" href="classCoveringAlgorithm.html#a17d51abd33df8a318074b115abecc91f">mcrCoverSort</a> (<a class="el" href="classGraph.html">Graph</a> *g, long **cover, <a class="el" href="classFactory.html">Factory</a>&lt; T &gt; *factory, long *R, long r)</td></tr>
<tr class="memdesc:a17d51abd33df8a318074b115abecc91f"><td class="mdescLeft">&#160;</td><td class="mdescRight">Cover the vertexes of the graph according its degree and the degree of its neighbours.  <a href="#a17d51abd33df8a318074b115abecc91f"></a><br/></td></tr>
<tr class="memitem:a518e172a59843abebc06fabd2d001f4b"><td class="memTemplParams" colspan="2">template&lt;class T &gt; </td></tr>
<tr class="memitem:a518e172a59843abebc06fabd2d001f4b"><td class="memTemplItemLeft" align="right" valign="top">static long&#160;</td><td class="memTemplItemRight" valign="bottom"><a class="el" href="classCoveringAlgorithm.html#a518e172a59843abebc06fabd2d001f4b">greedySort</a> (<a class="el" href="classGraph.html">Graph</a> *g, long **cover, <a class="el" href="classFactory.html">Factory</a>&lt; T &gt; *factory, long *R, long r, long **Ro)</td></tr>
<tr class="memdesc:a518e172a59843abebc06fabd2d001f4b"><td class="mdescLeft">&#160;</td><td class="mdescRight">Made a greedy coloring of the subgraph induced by the vertexes in R, with the order that they appear in R.  <a href="#a518e172a59843abebc06fabd2d001f4b"></a><br/></td></tr>
<tr class="memitem:af3d74c747d2e761a3d9ea0b12864fffc"><td class="memTemplParams" colspan="2">template&lt;class T &gt; </td></tr>
<tr class="memitem:af3d74c747d2e761a3d9ea0b12864fffc"><td class="memTemplItemLeft" align="right" valign="top">static long&#160;</td><td class="memTemplItemRight" valign="bottom"><a class="el" href="classCoveringAlgorithm.html#af3d74c747d2e761a3d9ea0b12864fffc">dsaturSort</a> (<a class="el" href="classGraph.html">Graph</a> *g, long **cover, <a class="el" href="classFactory.html">Factory</a>&lt; T &gt; *factory, long *R, long r, long **Ro)</td></tr>
<tr class="memdesc:af3d74c747d2e761a3d9ea0b12864fffc"><td class="mdescLeft">&#160;</td><td class="mdescRight">Made a greedy coloring of the subgraph induced by the vertexes in R, using the DSatur algorithm.  <a href="#af3d74c747d2e761a3d9ea0b12864fffc"></a><br/></td></tr>
<tr class="memitem:a6c3363069bd85f182d6c9ce371a7e5b0"><td class="memTemplParams" colspan="2">template&lt;class T &gt; </td></tr>
<tr class="memitem:a6c3363069bd85f182d6c9ce371a7e5b0"><td class="memTemplItemLeft" align="right" valign="top">static long&#160;</td><td class="memTemplItemRight" valign="bottom"><a class="el" href="classCoveringAlgorithm.html#a6c3363069bd85f182d6c9ce371a7e5b0">mcrSort</a> (<a class="el" href="classGraph.html">Graph</a> *g, long **cover, <a class="el" href="classFactory.html">Factory</a>&lt; T &gt; *factory, long *R, long r, long **Ro)</td></tr>
<tr class="memdesc:a6c3363069bd85f182d6c9ce371a7e5b0"><td class="mdescLeft">&#160;</td><td class="mdescRight">Order the vertexes of the graph according its degree and the degree of its neighbours.  <a href="#a6c3363069bd85f182d6c9ce371a7e5b0"></a><br/></td></tr>
<tr class="memitem:a3fdba0a488582f11831e64c5e78ac4d4"><td class="memTemplParams" colspan="2">template&lt;class T &gt; </td></tr>
<tr class="memitem:a3fdba0a488582f11831e64c5e78ac4d4"><td class="memTemplItemLeft" align="right" valign="top">static long&#160;</td><td class="memTemplItemRight" valign="bottom"><a class="el" href="classCoveringAlgorithm.html#a3fdba0a488582f11831e64c5e78ac4d4">connectedComponents</a> (<a class="el" href="classGraph.html">Graph</a> *g, T **comp, <a class="el" href="classFactory.html">Factory</a>&lt; T &gt; *factory)</td></tr>
<tr class="memdesc:a3fdba0a488582f11831e64c5e78ac4d4"><td class="mdescLeft">&#160;</td><td class="mdescRight">Determine the connected components of a graph.  <a href="#a3fdba0a488582f11831e64c5e78ac4d4"></a><br/></td></tr>
<tr class="memitem:a8c0da9b67fb3e825669a97e264db9fa1"><td class="memTemplParams" colspan="2">template&lt;class T &gt; </td></tr>
<tr class="memitem:a8c0da9b67fb3e825669a97e264db9fa1"><td class="memTemplItemLeft" align="right" valign="top">static long&#160;</td><td class="memTemplItemRight" valign="bottom"><a class="el" href="classCoveringAlgorithm.html#a8c0da9b67fb3e825669a97e264db9fa1">connectedComponents</a> (<a class="el" href="classGraph.html">Graph</a> *g, long *comp, <a class="el" href="classFactory.html">Factory</a>&lt; T &gt; *factory)</td></tr>
<tr class="memdesc:a8c0da9b67fb3e825669a97e264db9fa1"><td class="mdescLeft">&#160;</td><td class="mdescRight">Determine the connected components of a graph.  <a href="#a8c0da9b67fb3e825669a97e264db9fa1"></a><br/></td></tr>
<tr class="memitem:a6dbcad00881699e4871d9be3d74c9c21"><td class="memTemplParams" colspan="2">template&lt;class T &gt; </td></tr>
<tr class="memitem:a6dbcad00881699e4871d9be3d74c9c21"><td class="memTemplItemLeft" align="right" valign="top">static <a class="el" href="classDiGraph.html">DiGraph</a> *&#160;</td><td class="memTemplItemRight" valign="bottom"><a class="el" href="classCoveringAlgorithm.html#a6dbcad00881699e4871d9be3d74c9c21">readDimacsGraph</a> (FILE *graphFile, <a class="el" href="Graph_8h.html#aa2142693629eb28bcfd13af8886f2786">graphType</a> t, <a class="el" href="classFactory.html">Factory</a>&lt; T &gt; *factory, void *handle)</td></tr>
<tr class="memdesc:a6dbcad00881699e4871d9be3d74c9c21"><td class="mdescLeft">&#160;</td><td class="mdescRight">Reads a graph from a file.  <a href="#a6dbcad00881699e4871d9be3d74c9c21"></a><br/></td></tr>
<tr class="memitem:a01db0aee52349dc97c8cd640d736d520"><td class="memItemLeft" align="right" valign="top">static long&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="classCoveringAlgorithm.html#a01db0aee52349dc97c8cd640d736d520">greedySort</a> (<a class="el" href="classGraph.html">Graph</a> *g, long *d, long **ng, long k, long *rank)</td></tr>
<tr class="memitem:a88551c513fa0637bf153574f3e2a9bd1"><td class="memItemLeft" align="right" valign="top">static long&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="classCoveringAlgorithm.html#a88551c513fa0637bf153574f3e2a9bd1">greedyCoverSort</a> (<a class="el" href="classGraph.html">Graph</a> *g, long k, long *rank)</td></tr>
<tr class="memitem:af2c44d69944267da636a0d7cf0a0f6ec"><td class="memItemLeft" align="right" valign="top">static long&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="classCoveringAlgorithm.html#af2c44d69944267da636a0d7cf0a0f6ec">dsaturSort</a> (<a class="el" href="classGraph.html">Graph</a> *g, long *d, long **ng, long k, long *rank)</td></tr>
<tr class="memitem:aa267a3cec4e1c906b6e54c366181ec43"><td class="memItemLeft" align="right" valign="top">static long&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="classCoveringAlgorithm.html#aa267a3cec4e1c906b6e54c366181ec43">dsaturCoverSort</a> (<a class="el" href="classGraph.html">Graph</a> *g, long k, long *rank)</td></tr>
<tr class="memitem:a9fc3d684b38b122a8dfc6e9530b6cb6d"><td class="memItemLeft" align="right" valign="top">static bool&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="classCoveringAlgorithm.html#a9fc3d684b38b122a8dfc6e9530b6cb6d">mcrSort</a> (<a class="el" href="classGraph.html">Graph</a> *g, long *d, long **ng, long *rank)</td></tr>
<tr class="memitem:aa6d428e7c8d8ed6b5f976cd8147253b8"><td class="memItemLeft" align="right" valign="top">static bool&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="classCoveringAlgorithm.html#aa6d428e7c8d8ed6b5f976cd8147253b8">mcrDegreeSort</a> (<a class="el" href="classGraph.html">Graph</a> *g, long *maxd, long *rank)</td></tr>
<tr class="memitem:a3585c1273b26afe7a22ba884286b4116"><td class="memItemLeft" align="right" valign="top">static double&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="classCoveringAlgorithm.html#a3585c1273b26afe7a22ba884286b4116">FCP2</a> (<a class="el" href="classGraph.html">Graph</a> *g, long k, long **rank)</td></tr>
</table>
<hr/><h2>Member Function Documentation</h2>
<a class="anchor" id="a3fdba0a488582f11831e64c5e78ac4d4"></a>
<div class="memitem">
<div class="memproto">
<div class="memtemplate">
template&lt;class T &gt; </div>
<table class="mlabels">
  <tr>
  <td class="mlabels-left">
      <table class="memname">
        <tr>
          <td class="memname">long CoveringAlgorithm::connectedComponents&lt; T &gt; </td>
          <td>(</td>
          <td class="paramtype"><a class="el" href="classGraph.html">Graph</a> *&#160;</td>
          <td class="paramname"><em>g</em>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype">T **&#160;</td>
          <td class="paramname"><em>comp</em>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype"><a class="el" href="classFactory.html">Factory</a>&lt; T &gt; *&#160;</td>
          <td class="paramname"><em>factory</em>&#160;</td>
        </tr>
        <tr>
          <td></td>
          <td>)</td>
          <td></td><td></td>
        </tr>
      </table>
  </td>
  <td class="mlabels-right">
<span class="mlabels"><span class="mlabel">static</span></span>  </td>
  </tr>
</table>
</div><div class="memdoc">

<p>Determine the connected components of a graph. </p>
<p>Determine the connected components of a graph. A connected component of a graph is a maximal subgraph such that for each pair u, v belong to the subgraph, there is a path between then in the subgraph.</p>
<p>The connected components are view as a matrix of adjacency. comp is a matrix of bits, such that comp[i] is a bit array representing the vertexes belonging to that component.</p>
<dl class="params"><dt>Parameters:</dt><dd>
  <table class="params">
    <tr><td class="paramname">g</td><td>the graph.</td></tr>
    <tr><td class="paramname">comp</td><td>the connected components of g as a matrix of adjacency.</td></tr>
    <tr><td class="paramname">factory</td><td>a abstract factory to sets used to instance the objects used.</td></tr>
  </table>
  </dd>
</dl>
<dl class="section return"><dt>Returns:</dt><dd>the number of connected components in the graph g. </dd></dl>
<dl class="tparams"><dt>Template Parameters:</dt><dd>
  <table class="tparams">
    <tr><td class="paramname">T</td><td>define the bitmap directly addressed sets </td></tr>
  </table>
  </dd>
</dl>

</div>
</div>
<a class="anchor" id="a8c0da9b67fb3e825669a97e264db9fa1"></a>
<div class="memitem">
<div class="memproto">
<div class="memtemplate">
template&lt;class T &gt; </div>
<table class="mlabels">
  <tr>
  <td class="mlabels-left">
      <table class="memname">
        <tr>
          <td class="memname">long CoveringAlgorithm::connectedComponents&lt; T &gt; </td>
          <td>(</td>
          <td class="paramtype"><a class="el" href="classGraph.html">Graph</a> *&#160;</td>
          <td class="paramname"><em>g</em>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype">long *&#160;</td>
          <td class="paramname"><em>comp</em>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype"><a class="el" href="classFactory.html">Factory</a>&lt; T &gt; *&#160;</td>
          <td class="paramname"><em>factory</em>&#160;</td>
        </tr>
        <tr>
          <td></td>
          <td>)</td>
          <td></td><td></td>
        </tr>
      </table>
  </td>
  <td class="mlabels-right">
<span class="mlabels"><span class="mlabel">static</span></span>  </td>
  </tr>
</table>
</div><div class="memdoc">

<p>Determine the connected components of a graph. </p>
<p>Determine the connected components of a graph. A connected component of a graph is a maximal subgraph such that for each pair u, v belong to the subgraph, there is a path between then in the subgraph.</p>
<p>The connected components are view as a array. comp is a vector of integer, such that comp[i] indicates the connected component each the vertex i belong.</p>
<dl class="params"><dt>Parameters:</dt><dd>
  <table class="params">
    <tr><td class="paramname">g</td><td>the graph.</td></tr>
    <tr><td class="paramname">comp</td><td>the conected components of g as a caracteristic vector.</td></tr>
    <tr><td class="paramname">factory</td><td>a abstratc factory to sets used to instance the objects used.</td></tr>
  </table>
  </dd>
</dl>
<dl class="section return"><dt>Returns:</dt><dd>the number of connected components in the graph g. </dd></dl>
<dl class="tparams"><dt>Template Parameters:</dt><dd>
  <table class="tparams">
    <tr><td class="paramname">T</td><td>define the bitmap directly addressed sets </td></tr>
  </table>
  </dd>
</dl>

</div>
</div>
<a class="anchor" id="a93b9589e1dba6b3533bea7e30a03bf6f"></a>
<div class="memitem">
<div class="memproto">
<div class="memtemplate">
template&lt;typename T , template&lt; typename T &gt; class D&gt; </div>
<table class="mlabels">
  <tr>
  <td class="mlabels-left">
      <table class="memname">
        <tr>
          <td class="memname">long CoveringAlgorithm::dsaturCoverSort&lt; T, D &gt; </td>
          <td>(</td>
          <td class="paramtype">long&#160;</td>
          <td class="paramname"><em>n</em>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype"><a class="el" href="classFactory.html">Factory</a>&lt; D &gt; *&#160;</td>
          <td class="paramname"><em>factory</em>&#160;</td>
        </tr>
        <tr>
          <td></td>
          <td>)</td>
          <td></td><td></td>
        </tr>
      </table>
  </td>
  <td class="mlabels-right">
<span class="mlabels"><span class="mlabel">static</span></span>  </td>
  </tr>
</table>
</div><div class="memdoc">

<p>Determines a greedy coloring of the subgraph induced by the specified vertices using the <a class="el" href="classDsatur.html">Dsatur</a> algorithm. </p>
<p>The order used to guide the greedy coloring is specified by a function given as input. The <a class="el" href="classDsatur.html">Dsatur</a> algorithm keeps track of the so called saturation degree of each vertex. The saturation degree of a vertex <code>v</code> is the number of already colored vertices in the neighborhood of <code>v</code>. At each iteration, the uncolored vertex with the largest saturation degree (with the largest degree used to break ties, whenever possible) is chosen to be colored.</p>
<dl class="params"><dt>Parameters:</dt><dd>
  <table class="params">
    <tr><td class="paramname">g</td><td>the input graph </td></tr>
    <tr><td class="paramname">cover</td><td>the vector in which the colors are returned: the position <code>i</code> in this vector indicates the color of the vertex <code>R</code>[i] in the greedy coloring of the subgraph induced by <code>R</code>. </td></tr>
    <tr><td class="paramname">factory</td><td>a factory to <a class="el" href="classBitMapDirectlyAddressedSet.html" title="A DirectlyAddressedSet implemented with an array of nodes, each node corresponding to a word of the s...">BitMapDirectlyAddressedSet</a> to be used to instantiate the variables. </td></tr>
    <tr><td class="paramname">R</td><td>a vector representing the verticees to be colored and the order to be used to color them. </td></tr>
    <tr><td class="paramname">r</td><td>the number of verticees in the subgraph.</td></tr>
  </table>
  </dd>
</dl>
<dl class="section return"><dt>Returns:</dt><dd>the number of colors used in the greedy coloring of the subgraph induced by <code>R</code> returned in <code>cover</code> </dd></dl>
<dl class="tparams"><dt>Template Parameters:</dt><dd>
  <table class="tparams">
    <tr><td class="paramname">T</td><td>define the bitmap directly addressed sets</td></tr>
  </table>
  </dd>
</dl>
<dl class="section see"><dt>See also:</dt><dd><a href="http://www.math.tu-clausthal.de/Arbeitsgruppen/Diskrete-Optimierung/publications/2002/gca.pdf">http://www.math.tu-clausthal.de/Arbeitsgruppen/Diskrete-Optimierung/publications/2002/gca.pdf</a> </dd></dl>

</div>
</div>
<a class="anchor" id="aa267a3cec4e1c906b6e54c366181ec43"></a>
<div class="memitem">
<div class="memproto">
<table class="mlabels">
  <tr>
  <td class="mlabels-left">
      <table class="memname">
        <tr>
          <td class="memname">static long CoveringAlgorithm::dsaturCoverSort </td>
          <td>(</td>
          <td class="paramtype"><a class="el" href="classGraph.html">Graph</a> *&#160;</td>
          <td class="paramname"><em>g</em>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype">long&#160;</td>
          <td class="paramname"><em>k</em>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype">long *&#160;</td>
          <td class="paramname"><em>rank</em>&#160;</td>
        </tr>
        <tr>
          <td></td>
          <td>)</td>
          <td></td><td></td>
        </tr>
      </table>
  </td>
  <td class="mlabels-right">
<span class="mlabels"><span class="mlabel">static</span></span>  </td>
  </tr>
</table>
</div><div class="memdoc">
<dl class="params"><dt>Parameters:</dt><dd>
  <table class="params">
    <tr><td class="paramname">g</td><td></td></tr>
    <tr><td class="paramname">k</td><td></td></tr>
    <tr><td class="paramname">rank</td><td></td></tr>
  </table>
  </dd>
</dl>
<dl class="section return"><dt>Returns:</dt><dd></dd></dl>

</div>
</div>
<a class="anchor" id="aabf673011d19a85d51789efa556b0f5c"></a>
<div class="memitem">
<div class="memproto">
<div class="memtemplate">
template&lt;class T , typename Z&gt; </div>
      <table class="memname">
        <tr>
          <td class="memname">long CoveringAlgorithm::dsaturCoverSort </td>
          <td>(</td>
          <td class="paramtype"><a class="el" href="classGraph.html">Graph</a>&lt; T &gt; *&#160;</td>
          <td class="paramname"><em>g</em>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype">long&#160;</td>
          <td class="paramname"><em>k</em>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype">long *&#160;</td>
          <td class="paramname"><em>rank</em>&#160;</td>
        </tr>
        <tr>
          <td></td>
          <td>)</td>
          <td></td><td></td>
        </tr>
      </table>
</div><div class="memdoc">

</div>
</div>
<a class="anchor" id="af3d74c747d2e761a3d9ea0b12864fffc"></a>
<div class="memitem">
<div class="memproto">
<div class="memtemplate">
template&lt;class T &gt; </div>
<table class="mlabels">
  <tr>
  <td class="mlabels-left">
      <table class="memname">
        <tr>
          <td class="memname">long CoveringAlgorithm::dsaturSort&lt; T &gt; </td>
          <td>(</td>
          <td class="paramtype"><a class="el" href="classGraph.html">Graph</a> *&#160;</td>
          <td class="paramname"><em>g</em>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype">long **&#160;</td>
          <td class="paramname"><em>cover</em>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype"><a class="el" href="classFactory.html">Factory</a>&lt; T &gt; *&#160;</td>
          <td class="paramname"><em>factory</em>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype">long *&#160;</td>
          <td class="paramname"><em>R</em>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype">long&#160;</td>
          <td class="paramname"><em>r</em>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype">long **&#160;</td>
          <td class="paramname"><em>Ro</em>&#160;</td>
        </tr>
        <tr>
          <td></td>
          <td>)</td>
          <td></td><td></td>
        </tr>
      </table>
  </td>
  <td class="mlabels-right">
<span class="mlabels"><span class="mlabel">static</span></span>  </td>
  </tr>
</table>
</div><div class="memdoc">

<p>Made a greedy coloring of the subgraph induced by the vertexes in R, using the DSatur algorithm. </p>
<p>Made a greedy coloring of the subgraph induced by the vertexes in R. The order used to do this coloring is determinate by an other algorithm, the <a class="el" href="classDsatur.html">Dsatur</a> algorithm that keep track of the so called saturation degree of each vertex.</p>
<p>The saturation degree of v is the number of already colored vertexes in the neighbourhood of iv. In each step the algorithm choose the vertex in R with the biggest saturation degree, in case of tie it choose the one with biggest degree. The vertexes are colored in this order.</p>
<p>The vertexes will be order in Ro according to the colors that each one receive, and cover[i] represents the color of the vertex Ro[i].</p>
<dl class="params"><dt>Parameters:</dt><dd>
  <table class="params">
    <tr><td class="paramname">g</td><td>the graph.</td></tr>
    <tr><td class="paramname">cover</td><td>the vector of colors to each vertex of R, the position i in this vetor indicates de color of the vertex Ro[i] in the greedy coloring of the subgraph induced by R.</td></tr>
    <tr><td class="paramname">factory</td><td>a factory to OrderedSet to be used to instance the variables.</td></tr>
    <tr><td class="paramname">R</td><td>a vector representing the vertexes to be colored and the order to be used to color then.</td></tr>
    <tr><td class="paramname">r</td><td>the number of vertexes in the subgraph.</td></tr>
    <tr><td class="paramname">Ro</td><td>the vertexes of R ordered according its colors.</td></tr>
  </table>
  </dd>
</dl>
<dl class="section return"><dt>Returns:</dt><dd>the number of colors used to make a greedy coloring of the subgraph induced by R </dd></dl>
<dl class="tparams"><dt>Template Parameters:</dt><dd>
  <table class="tparams">
    <tr><td class="paramname">T</td><td>define the bitmap directly addressed sets </td></tr>
  </table>
  </dd>
</dl>

</div>
</div>
<a class="anchor" id="af2c44d69944267da636a0d7cf0a0f6ec"></a>
<div class="memitem">
<div class="memproto">
<table class="mlabels">
  <tr>
  <td class="mlabels-left">
      <table class="memname">
        <tr>
          <td class="memname">static long CoveringAlgorithm::dsaturSort </td>
          <td>(</td>
          <td class="paramtype"><a class="el" href="classGraph.html">Graph</a> *&#160;</td>
          <td class="paramname"><em>g</em>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype">long *&#160;</td>
          <td class="paramname"><em>d</em>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype">long **&#160;</td>
          <td class="paramname"><em>ng</em>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype">long&#160;</td>
          <td class="paramname"><em>k</em>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype">long *&#160;</td>
          <td class="paramname"><em>rank</em>&#160;</td>
        </tr>
        <tr>
          <td></td>
          <td>)</td>
          <td></td><td></td>
        </tr>
      </table>
  </td>
  <td class="mlabels-right">
<span class="mlabels"><span class="mlabel">static</span></span>  </td>
  </tr>
</table>
</div><div class="memdoc">
<dl class="params"><dt>Parameters:</dt><dd>
  <table class="params">
    <tr><td class="paramname">g</td><td></td></tr>
    <tr><td class="paramname">d</td><td></td></tr>
    <tr><td class="paramname">ng</td><td></td></tr>
    <tr><td class="paramname">k</td><td></td></tr>
    <tr><td class="paramname">rank</td><td></td></tr>
  </table>
  </dd>
</dl>
<dl class="section return"><dt>Returns:</dt><dd></dd></dl>

</div>
</div>
<a class="anchor" id="a3585c1273b26afe7a22ba884286b4116"></a>
<div class="memitem">
<div class="memproto">
<table class="mlabels">
  <tr>
  <td class="mlabels-left">
      <table class="memname">
        <tr>
          <td class="memname">static double CoveringAlgorithm::FCP2 </td>
          <td>(</td>
          <td class="paramtype"><a class="el" href="classGraph.html">Graph</a> *&#160;</td>
          <td class="paramname"><em>g</em>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype">long&#160;</td>
          <td class="paramname"><em>k</em>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype">long **&#160;</td>
          <td class="paramname"><em>rank</em>&#160;</td>
        </tr>
        <tr>
          <td></td>
          <td>)</td>
          <td></td><td></td>
        </tr>
      </table>
  </td>
  <td class="mlabels-right">
<span class="mlabels"><span class="mlabel">static</span></span>  </td>
  </tr>
</table>
</div><div class="memdoc">
<dl class="params"><dt>Parameters:</dt><dd>
  <table class="params">
    <tr><td class="paramname">g</td><td></td></tr>
    <tr><td class="paramname">k</td><td></td></tr>
    <tr><td class="paramname">rank</td><td></td></tr>
  </table>
  </dd>
</dl>
<dl class="section return"><dt>Returns:</dt><dd></dd></dl>

</div>
</div>
<a class="anchor" id="a22e739e175eaef6218f9a489528488ba"></a>
<div class="memitem">
<div class="memproto">
<div class="memtemplate">
template&lt;class T &gt; </div>
<table class="mlabels">
  <tr>
  <td class="mlabels-left">
      <table class="memname">
        <tr>
          <td class="memname">long CoveringAlgorithm::greedyCoverSort&lt; T &gt; </td>
          <td>(</td>
          <td class="paramtype"><a class="el" href="classGraph.html">Graph</a> *&#160;</td>
          <td class="paramname"><em>g</em>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype">long **&#160;</td>
          <td class="paramname"><em>cover</em>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype"><a class="el" href="classFactory.html">Factory</a>&lt; T &gt; *&#160;</td>
          <td class="paramname"><em>factory</em>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype">long *&#160;</td>
          <td class="paramname"><em>R</em>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype">long&#160;</td>
          <td class="paramname"><em>r</em>&#160;</td>
        </tr>
        <tr>
          <td></td>
          <td>)</td>
          <td></td><td></td>
        </tr>
      </table>
  </td>
  <td class="mlabels-right">
<span class="mlabels"><span class="mlabel">static</span></span>  </td>
  </tr>
</table>
</div><div class="memdoc">

<p>Made a greedy coloring of the subgraph induced by the vertexes in R, with the order that they appear in R. </p>
<p>Made a coloring, greedy coloring of the subgraph induced by the vertexes in R. The order used to built suc coloring is the same order that the vertexes appear in R. The algorithm visit each element in R, in order, and look for the smallest color not used in one of its neighbours to color it. If there is not such color a new color will be add to the set of possible colors.</p>
<dl class="params"><dt>Parameters:</dt><dd>
  <table class="params">
    <tr><td class="paramname">g</td><td>the graph. </td></tr>
    <tr><td class="paramname">cover</td><td>the vector of colors to each vertex of R, the position i in this vector indicates the color of the vertex R[i] in the greedy coloring of the subgraph induced by R. </td></tr>
    <tr><td class="paramname">factory</td><td>a factory to OrderedSet to be used to instance the variables. </td></tr>
    <tr><td class="paramname">R</td><td>a vector representing the vertexes to be colored and the order to be used to color then. </td></tr>
    <tr><td class="paramname">r</td><td>the number of vertexes in the subgraph.</td></tr>
  </table>
  </dd>
</dl>
<dl class="section return"><dt>Returns:</dt><dd>the number of colors used to make a greedy coloring of the subgraph induced by R </dd></dl>
<dl class="tparams"><dt>Template Parameters:</dt><dd>
  <table class="tparams">
    <tr><td class="paramname">T</td><td>define the bitmap directly addressed sets </td></tr>
  </table>
  </dd>
</dl>

</div>
</div>
<a class="anchor" id="a88551c513fa0637bf153574f3e2a9bd1"></a>
<div class="memitem">
<div class="memproto">
<table class="mlabels">
  <tr>
  <td class="mlabels-left">
      <table class="memname">
        <tr>
          <td class="memname">static long CoveringAlgorithm::greedyCoverSort </td>
          <td>(</td>
          <td class="paramtype"><a class="el" href="classGraph.html">Graph</a> *&#160;</td>
          <td class="paramname"><em>g</em>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype">long&#160;</td>
          <td class="paramname"><em>k</em>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype">long *&#160;</td>
          <td class="paramname"><em>rank</em>&#160;</td>
        </tr>
        <tr>
          <td></td>
          <td>)</td>
          <td></td><td></td>
        </tr>
      </table>
  </td>
  <td class="mlabels-right">
<span class="mlabels"><span class="mlabel">static</span></span>  </td>
  </tr>
</table>
</div><div class="memdoc">
<dl class="params"><dt>Parameters:</dt><dd>
  <table class="params">
    <tr><td class="paramname">g</td><td></td></tr>
    <tr><td class="paramname">k</td><td></td></tr>
    <tr><td class="paramname">rank</td><td></td></tr>
  </table>
  </dd>
</dl>
<dl class="section return"><dt>Returns:</dt><dd></dd></dl>

</div>
</div>
<a class="anchor" id="a518e172a59843abebc06fabd2d001f4b"></a>
<div class="memitem">
<div class="memproto">
<div class="memtemplate">
template&lt;class T &gt; </div>
<table class="mlabels">
  <tr>
  <td class="mlabels-left">
      <table class="memname">
        <tr>
          <td class="memname">long CoveringAlgorithm::greedySort&lt; T &gt; </td>
          <td>(</td>
          <td class="paramtype"><a class="el" href="classGraph.html">Graph</a> *&#160;</td>
          <td class="paramname"><em>g</em>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype">long **&#160;</td>
          <td class="paramname"><em>cover</em>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype"><a class="el" href="classFactory.html">Factory</a>&lt; T &gt; *&#160;</td>
          <td class="paramname"><em>factory</em>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype">long *&#160;</td>
          <td class="paramname"><em>R</em>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype">long&#160;</td>
          <td class="paramname"><em>r</em>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype">long **&#160;</td>
          <td class="paramname"><em>Ro</em>&#160;</td>
        </tr>
        <tr>
          <td></td>
          <td>)</td>
          <td></td><td></td>
        </tr>
      </table>
  </td>
  <td class="mlabels-right">
<span class="mlabels"><span class="mlabel">static</span></span>  </td>
  </tr>
</table>
</div><div class="memdoc">

<p>Made a greedy coloring of the subgraph induced by the vertexes in R, with the order that they appear in R. </p>
<p>Made a coloring, greedy coloring of the subgraph induced by the vertexes in R. The order used to built suc coloring is the same order that the vertexes appear in R. The algorithm visit each element in R, in order, and look for the smallest color not used in one of its neighbours to color it. If there is not such color a new color will be add to the set of possible colors.</p>
<p>The vertexes will be order in Ro according to the colors that each one receive, and cover[i] represents the color of the vertex Ro[i].</p>
<dl class="params"><dt>Parameters:</dt><dd>
  <table class="params">
    <tr><td class="paramname">g</td><td>the graph.</td></tr>
    <tr><td class="paramname">cover</td><td>the vector of colors to each vertex of R, the position i in this vector indicates the color of the vertex Ro[i] in the greedy coloring of the subgraph induced by R.</td></tr>
    <tr><td class="paramname">factory</td><td>a factory to OrderedSet to be used to instance the variables.</td></tr>
    <tr><td class="paramname">R</td><td>a vector representing the vertexes to be colored and the order to be used to color then.</td></tr>
    <tr><td class="paramname">r</td><td>the number of vertexes in the subgraph.</td></tr>
    <tr><td class="paramname">Ro</td><td>the vertexes of R ordered according its colors.</td></tr>
  </table>
  </dd>
</dl>
<dl class="section return"><dt>Returns:</dt><dd>the number of colors used to make a greedy coloring of the subgraph induced by R </dd></dl>
<dl class="tparams"><dt>Template Parameters:</dt><dd>
  <table class="tparams">
    <tr><td class="paramname">T</td><td>define the bitmap directly addressed sets </td></tr>
  </table>
  </dd>
</dl>

</div>
</div>
<a class="anchor" id="a01db0aee52349dc97c8cd640d736d520"></a>
<div class="memitem">
<div class="memproto">
<table class="mlabels">
  <tr>
  <td class="mlabels-left">
      <table class="memname">
        <tr>
          <td class="memname">static long CoveringAlgorithm::greedySort </td>
          <td>(</td>
          <td class="paramtype"><a class="el" href="classGraph.html">Graph</a> *&#160;</td>
          <td class="paramname"><em>g</em>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype">long *&#160;</td>
          <td class="paramname"><em>d</em>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype">long **&#160;</td>
          <td class="paramname"><em>ng</em>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype">long&#160;</td>
          <td class="paramname"><em>k</em>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype">long *&#160;</td>
          <td class="paramname"><em>rank</em>&#160;</td>
        </tr>
        <tr>
          <td></td>
          <td>)</td>
          <td></td><td></td>
        </tr>
      </table>
  </td>
  <td class="mlabels-right">
<span class="mlabels"><span class="mlabel">static</span></span>  </td>
  </tr>
</table>
</div><div class="memdoc">
<dl class="params"><dt>Parameters:</dt><dd>
  <table class="params">
    <tr><td class="paramname">g</td><td></td></tr>
    <tr><td class="paramname">d</td><td></td></tr>
    <tr><td class="paramname">ng</td><td></td></tr>
    <tr><td class="paramname">k</td><td></td></tr>
    <tr><td class="paramname">rank</td><td></td></tr>
  </table>
  </dd>
</dl>
<dl class="section return"><dt>Returns:</dt><dd></dd></dl>

</div>
</div>
<a class="anchor" id="a17d51abd33df8a318074b115abecc91f"></a>
<div class="memitem">
<div class="memproto">
<div class="memtemplate">
template&lt;class T &gt; </div>
<table class="mlabels">
  <tr>
  <td class="mlabels-left">
      <table class="memname">
        <tr>
          <td class="memname">long CoveringAlgorithm::mcrCoverSort&lt; T &gt; </td>
          <td>(</td>
          <td class="paramtype"><a class="el" href="classGraph.html">Graph</a> *&#160;</td>
          <td class="paramname"><em>g</em>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype">long **&#160;</td>
          <td class="paramname"><em>cover</em>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype"><a class="el" href="classFactory.html">Factory</a>&lt; T &gt; *&#160;</td>
          <td class="paramname"><em>factory</em>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype">long *&#160;</td>
          <td class="paramname"><em>R</em>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype">long&#160;</td>
          <td class="paramname"><em>r</em>&#160;</td>
        </tr>
        <tr>
          <td></td>
          <td>)</td>
          <td></td><td></td>
        </tr>
      </table>
  </td>
  <td class="mlabels-right">
<span class="mlabels"><span class="mlabel">static</span></span>  </td>
  </tr>
</table>
</div><div class="memdoc">

<p>Cover the vertexes of the graph according its degree and the degree of its neighbours. </p>
<p>Return an order to the vertexes in R, according the degrees in the subgraph induced for it. More clearly, if cover[i] = j it means that in the graph induced by the vertexes R[k] that has cover[k] &lt; j, R[i] is a vertex with minimum degree.</p>
<p>The integer value returned by this function is the biggest k such that k is the minimum degree in the subgraph induced by R[0] .... R[i] for all i &lt; r.</p>
<dl class="params"><dt>Parameters:</dt><dd>
  <table class="params">
    <tr><td class="paramname">g</td><td>the graph</td></tr>
    <tr><td class="paramname">cover</td><td>represent the order over the vertexes of g, the position i of this vector indicate the position of the vertex i in the order.</td></tr>
    <tr><td class="paramname">R</td><td>a vector representing the vertexes to be colored and the order to be used to color then.</td></tr>
    <tr><td class="paramname">r</td><td>the number of vertexes in the subgraph.</td></tr>
    <tr><td class="paramname">factory</td><td>a factory to OrderedSet to be used to instance the variables.</td></tr>
  </table>
  </dd>
</dl>
<dl class="section return"><dt>Returns:</dt><dd>the maximum mininum degree in the subgraph. </dd></dl>
<dl class="tparams"><dt>Template Parameters:</dt><dd>
  <table class="tparams">
    <tr><td class="paramname">T</td><td>define the bitmap directly addressed sets </td></tr>
  </table>
  </dd>
</dl>

</div>
</div>
<a class="anchor" id="aa6d428e7c8d8ed6b5f976cd8147253b8"></a>
<div class="memitem">
<div class="memproto">
<table class="mlabels">
  <tr>
  <td class="mlabels-left">
      <table class="memname">
        <tr>
          <td class="memname">bool CoveringAlgorithm::mcrDegreeSort </td>
          <td>(</td>
          <td class="paramtype"><a class="el" href="classGraph.html">Graph</a> *&#160;</td>
          <td class="paramname"><em>g</em>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype">long *&#160;</td>
          <td class="paramname"><em>maxd</em>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype">long *&#160;</td>
          <td class="paramname"><em>rank</em>&#160;</td>
        </tr>
        <tr>
          <td></td>
          <td>)</td>
          <td></td><td></td>
        </tr>
      </table>
  </td>
  <td class="mlabels-right">
<span class="mlabels"><span class="mlabel">static</span></span>  </td>
  </tr>
</table>
</div><div class="memdoc">
<dl class="params"><dt>Parameters:</dt><dd>
  <table class="params">
    <tr><td class="paramname">g</td><td></td></tr>
    <tr><td class="paramname">maxd</td><td></td></tr>
    <tr><td class="paramname">rank</td><td></td></tr>
  </table>
  </dd>
</dl>
<dl class="section return"><dt>Returns:</dt><dd></dd></dl>

</div>
</div>
<a class="anchor" id="a6c3363069bd85f182d6c9ce371a7e5b0"></a>
<div class="memitem">
<div class="memproto">
<div class="memtemplate">
template&lt;class T &gt; </div>
<table class="mlabels">
  <tr>
  <td class="mlabels-left">
      <table class="memname">
        <tr>
          <td class="memname">long CoveringAlgorithm::mcrSort&lt; T &gt; </td>
          <td>(</td>
          <td class="paramtype"><a class="el" href="classGraph.html">Graph</a> *&#160;</td>
          <td class="paramname"><em>g</em>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype">long **&#160;</td>
          <td class="paramname"><em>cover</em>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype"><a class="el" href="classFactory.html">Factory</a>&lt; T &gt; *&#160;</td>
          <td class="paramname"><em>factory</em>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype">long *&#160;</td>
          <td class="paramname"><em>R</em>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype">long&#160;</td>
          <td class="paramname"><em>r</em>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype">long **&#160;</td>
          <td class="paramname"><em>Ro</em>&#160;</td>
        </tr>
        <tr>
          <td></td>
          <td>)</td>
          <td></td><td></td>
        </tr>
      </table>
  </td>
  <td class="mlabels-right">
<span class="mlabels"><span class="mlabel">static</span></span>  </td>
  </tr>
</table>
</div><div class="memdoc">

<p>Order the vertexes of the graph according its degree and the degree of its neighbours. </p>
<p>Return an order to the vertexes in R, according the degrees in the subgraph induced for it. More clearly, Ro[i] has the minimum degree in the subgraph induced by R[0]... R[i].</p>
<p>The integer value returned by this function is the biggest k such that k is the minimum degree in the subgraph induced by R[0] .... R[i] for all i &lt; r.</p>
<p>The array cover represent a upper bound to the size of the clique that can be generate from a specified position of Ro. For instance if cover[i] = j, the subgraph R[0]... R[i] has as upper bound for its maximum clique j.</p>
<dl class="params"><dt>Parameters:</dt><dd>
  <table class="params">
    <tr><td class="paramname">g</td><td>the graph</td></tr>
    <tr><td class="paramname">cover</td><td>represent the order over the vertexes of g, the position i of this vector indicate the position of the vertex i in the order.</td></tr>
    <tr><td class="paramname">R</td><td>a vector representing the vertexes to be colored and the order to be used to color then.</td></tr>
    <tr><td class="paramname">r</td><td>the number of vertexes in the subgraph.</td></tr>
    <tr><td class="paramname">factory</td><td>a factory to OrderedSet to be used to instance the variables.</td></tr>
    <tr><td class="paramname">Ro</td><td>the vertexes of R ordered according its degree and the deegre of its neighbours.</td></tr>
  </table>
  </dd>
</dl>
<dl class="section return"><dt>Returns:</dt><dd>the maximmum deegre of the vertexes in the graph. </dd></dl>
<dl class="tparams"><dt>Template Parameters:</dt><dd>
  <table class="tparams">
    <tr><td class="paramname">T</td><td>define the bitmap directly addressed sets </td></tr>
  </table>
  </dd>
</dl>

</div>
</div>
<a class="anchor" id="a9fc3d684b38b122a8dfc6e9530b6cb6d"></a>
<div class="memitem">
<div class="memproto">
<table class="mlabels">
  <tr>
  <td class="mlabels-left">
      <table class="memname">
        <tr>
          <td class="memname">static bool CoveringAlgorithm::mcrSort </td>
          <td>(</td>
          <td class="paramtype"><a class="el" href="classGraph.html">Graph</a> *&#160;</td>
          <td class="paramname"><em>g</em>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype">long *&#160;</td>
          <td class="paramname"><em>d</em>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype">long **&#160;</td>
          <td class="paramname"><em>ng</em>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype">long *&#160;</td>
          <td class="paramname"><em>rank</em>&#160;</td>
        </tr>
        <tr>
          <td></td>
          <td>)</td>
          <td></td><td></td>
        </tr>
      </table>
  </td>
  <td class="mlabels-right">
<span class="mlabels"><span class="mlabel">static</span></span>  </td>
  </tr>
</table>
</div><div class="memdoc">
<dl class="params"><dt>Parameters:</dt><dd>
  <table class="params">
    <tr><td class="paramname">g</td><td></td></tr>
    <tr><td class="paramname">d</td><td></td></tr>
    <tr><td class="paramname">ng</td><td></td></tr>
    <tr><td class="paramname">rank</td><td></td></tr>
  </table>
  </dd>
</dl>
<dl class="section return"><dt>Returns:</dt><dd></dd></dl>

</div>
</div>
<a class="anchor" id="a6dbcad00881699e4871d9be3d74c9c21"></a>
<div class="memitem">
<div class="memproto">
<div class="memtemplate">
template&lt;class T &gt; </div>
<table class="mlabels">
  <tr>
  <td class="mlabels-left">
      <table class="memname">
        <tr>
          <td class="memname"><a class="el" href="classDiGraph.html">DiGraph</a> * CoveringAlgorithm::readDimacsGraph&lt; T &gt; </td>
          <td>(</td>
          <td class="paramtype">FILE *&#160;</td>
          <td class="paramname"><em>graphFile</em>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype"><a class="el" href="Graph_8h.html#aa2142693629eb28bcfd13af8886f2786">graphType</a>&#160;</td>
          <td class="paramname"><em>t</em>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype"><a class="el" href="classFactory.html">Factory</a>&lt; T &gt; *&#160;</td>
          <td class="paramname"><em>factory</em>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype">void *&#160;</td>
          <td class="paramname"><em>handle</em>&#160;</td>
        </tr>
        <tr>
          <td></td>
          <td>)</td>
          <td></td><td></td>
        </tr>
      </table>
  </td>
  <td class="mlabels-right">
<span class="mlabels"><span class="mlabel">static</span></span>  </td>
  </tr>
</table>
</div><div class="memdoc">

<p>Reads a graph from a file. </p>
<p>The file must be in the DIMACS benchmark format, which means that it must start with a line <code>p</code> <code>x</code> <code>y</code> indicating the number of vertices <code>x</code> and the number of edges <code>y</code>. Each edge must be in a line starting with character <code>e</code> followed by the first endpoint of the edge plus space plus the second endpoint.</p>
<p>The file must have no blank lines and each edge must be in a single line. If the file is not in the DIMACS format an error will occur.</p>
<dl class="params"><dt>Parameters:</dt><dd>
  <table class="params">
    <tr><td class="paramname">graphFile</td><td>the file in a specified form to represent a graph </td></tr>
    <tr><td class="paramname">t</td><td>indicates if we read the graph or its complement </td></tr>
    <tr><td class="paramname">factory</td><td>an abstract factory used to instantiate the graph object </td></tr>
    <tr><td class="paramname">handle</td><td>additional parameters to be passed to the factory when the graph is instantiated</td></tr>
  </table>
  </dd>
</dl>
<dl class="section return"><dt>Returns:</dt><dd>the resulting graph </dd></dl>
<dl class="tparams"><dt>Template Parameters:</dt><dd>
  <table class="tparams">
    <tr><td class="paramname">T</td><td>define the returned graph </td></tr>
  </table>
  </dd>
</dl>

</div>
</div>
<a class="anchor" id="aed9685e459071f73af35dfafd116b133"></a>
<div class="memitem">
<div class="memproto">
<table class="mlabels">
  <tr>
  <td class="mlabels-left">
      <table class="memname">
        <tr>
          <td class="memname">long CoveringAlgorithm::run </td>
          <td>(</td>
          <td class="paramtype"><a class="el" href="classGraph.html">Graph</a> *&#160;</td>
          <td class="paramname"><em>g</em>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype">long *&#160;</td>
          <td class="paramname"><em>res</em>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype">long *&#160;</td>
          <td class="paramname"><em>R</em>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype">long&#160;</td>
          <td class="paramname"><em>r</em>&#160;</td>
        </tr>
        <tr>
          <td></td>
          <td>)</td>
          <td></td><td></td>
        </tr>
      </table>
  </td>
  <td class="mlabels-right">
<span class="mlabels"><span class="mlabel">pure virtual</span></span>  </td>
  </tr>
</table>
</div><div class="memdoc">

</div>
</div>
<hr/>The documentation for this class was generated from the following file:<ul>
<li>graphs/<a class="el" href="CoveringAlgorithm_8h_source.html">CoveringAlgorithm.h</a></li>
</ul>
</div><!-- contents -->
<!-- start footer part -->
<hr class="footer"/><address class="footer"><small>
Generated on Thu Nov 22 2012 08:25:18 for Data Structures for Sets and Graphs by &#160;<a href="http://www.doxygen.org/index.html">
<img class="footer" src="doxygen.png" alt="doxygen"/>
</a> 1.8.1.1
</small></address>
</body>
</html>
